package com.zzg.datastructure.binarysorttree.tree;

import com.zzg.datastructure.binarysorttree.entity.Node;
import lombok.Getter;

import java.util.Objects;

/**
 * @Author zhengzg
 * @Date 2022-09-30
 * @Version v1.0
 * 二叉排序树：对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大
 * 如果有相同的值，可以将该节点放在左子节点或右子节点
 */
@Getter
public class BinarySortTree {
    private Node root;

    // 查找要删除的节点
    public Node search(int value) {
        if (Objects.isNull(this.root)) {
            return null;
        } else {
            return root.search(value);
        }
    }

    // 查找父节点
    public Node searchParent(int value) {
        if (Objects.isNull(this.root)) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    /**
     * 返回的以node为根节点的二叉排序树的根节点
     * 删除node为根节点的二叉排序树的最小节点
     *
     * @param node 传入的节点
     * @return 以node为根节点的二叉排序树的最小节点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        // 循环查找左子节点，就会找到最小值
        while (Objects.nonNull(target.left)) {
            target = target.left;
        }
        // 这是target就指向了最小节点
        // 删除最小节点
        delNode(target.value);
        return target.value;
    }

    // 删除节点
    public void delNode(int value) {
        if (Objects.nonNull(root)) {
            // 1.需求先去找到要删除的节点 targetNode
            Node targetNode = search(value);
            // 如果没有找到要删除的节点
            if (Objects.isNull(targetNode)) {
                return;
            }
            // 如果我们发现当前这棵二叉排序树只有一个节点
            if (Objects.isNull(this.root.left) && Objects.isNull(this.root.right)) {
                this.root = null;
                return;
            }
            // 去找到targetNode的父节点
            Node parent = searchParent(value);
            // 如果要删除的节点是叶子节点
            if (Objects.isNull(targetNode.left) && Objects.isNull(targetNode.right)) {
                // 判断targetNode是父节点的左子节点，还是右子节点
                if (Objects.nonNull(parent.left) && parent.left.value == value) {
                    parent.left = null;
                } else if (Objects.nonNull(parent.right) && parent.right.value == value) {
                    parent.right = null;
                }
            } else if (Objects.nonNull(targetNode.left) && Objects.nonNull(targetNode.right)) {
                // 删除有两颗子树的节点
                /*
                 * 传入待删除节点的右子节点，在右子树中寻找最小值，注意：此时右子树中的任意子节点都大于待删除节点
                 * 的左子节点，所以找到最小的左子节点，将最小的节点的值赋值给待删除的节点，符合二叉树定义。且最小值
                 * 一定小于待删除节点的右子节点的右子节点
                 * 如果不懂可以手动画图，在12节点下增加11和13即可
                 */
                targetNode.value = delRightTreeMin(targetNode.right);
            } else {
                // 删除只有一颗子树的节点
                if (Objects.nonNull(targetNode.left)) {
                    if (Objects.nonNull(parent)) {
                        // 如果targetNode是parent的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            // targetNode 是parent的右子节点
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else {
                    // 如果要删除的节点有右子节点
                    if (Objects.nonNull(parent)) {
                        // 如果targetNode是parent的左子节点
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {
                            // targetNode 是parent的右子节点
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

    // 添加节点
    public void add(Node node) {
        if (Objects.isNull(root)) {
            root = node;
        } else {
            root.add(node);
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (Objects.isNull(root)) {
            System.out.println("空树，无法遍历~");
        } else {
            root.infixOrder();
        }
    }

}
